#include <iostream>
#define MAXSIZE 1000
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TURE 1
#define FAULT 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define KIND_GT 0
#define KIND_GE 1
#define KIND_LT 2
#define KIND_LE 3
#define KIND_EQ 4
#define KIND_NE 5

#define ElemType char
using namespace std;

typedef int Status;

typedef struct {
    ElemType *elem;
    int length;
    int listsize;
}Sqlist;

void print_list(Sqlist L, int begin=0, int end=0) {
    if (!end) {
        end = L.length;
    }
    if (begin<0 || end > L.length) {
        cout<<"Warning from function print_list: illegal begin or end "<<begin<<" "<<end<<endl;
        return;
    }
    for(int i = begin; i < end; ++i) cout<<"Element "<<i+1<<"==\t"<<L.elem[i]<<endl;
}

Status InitList_Sq(Sqlist &L) {
    L.elem=(ElemType *)malloc (LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem) exit(OVERFLOW);
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
}// InitList_Sq

Status ListInsert_Sq(Sqlist &L,int i,ElemType e) {
    if (i<1 || i>L.length+1) {
        cout<<"Waring from function ListInsert_Sq: illegal i\t"<<i<<endl;
        return ERROR;
    }

    if (L.length >= L.listsize) {
        ElemType *newbase;
        newbase = (ElemType *)realloc(L.elem,(LIST_INIT_SIZE + LISTINCREMENT)*sizeof(ElemType));
        if (!newbase) exit(OVERFLOW);
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }

    for (int j = L.length; j >= i; j--){
        L.elem[j] = L.elem[j-1];
    }
    L.elem[i-1]=e;

    L.length += 1;
    //cout<<"L.length == "<<L.length<<endl;
    return OK;
} //ListInsert_Sq

Status ListDelete_Sq(Sqlist &L, int i){
    if (i < 1 || i > L.length) {
        cout<<"Warning from function ListDelete: i is illegal\t"<<i<<endl;
        return ERROR;
    }
    for (int j = i-1; j < L.length-1; ++j){
        L.elem[j] = L.elem[j+1];
    }

    --L.length;
    return OK;
}

Status LocateElem_Sq(Sqlist L, ElemType e, int kind) {
    if      (kind == KIND_GT) {for (int i=0; i<L.length; ++i) if (L.elem[i] > e)  return i+1;}
    else if (kind == KIND_GE) {for (int i=0; i<L.length; ++i) if (L.elem[i] >= e) return i+1;}
    else if (kind == KIND_LT) {for (int i=0; i<L.length; ++i) if (L.elem[i] < e)  return i+1;}
    else if (kind == KIND_LE) {for (int i=0; i<L.length; ++i) if (L.elem[i] <= e) return i+1;}
    else if (kind == KIND_EQ) {for (int i=0; i<L.length; ++i) if (L.elem[i] == e) return i+1;}
    else if (kind == KIND_NE) {for (int i=0; i<L.length; ++i) if (L.elem[i] != e) return i+1;}
    else {
        cout<<"Warning from function compare: illegal kind "<<kind<<endl;
        return -1;
    }
    return 0;
}

void MergeList_Sq(Sqlist La, Sqlist Lb, Sqlist &Lc) {
    Lc.listsize = Lc.length = La.length + Lb.length;
    Lc.elem = (ElemType *)realloc(Lc.elem, Lc.listsize*sizeof(ElemType));
    int i = 0, j = 0, k = 0;
    while (i < La.length && j < Lb.length){
        if (La.elem[i] <= Lb.elem[j]) Lc.elem[k++]=La.elem[i++];
        else Lc.elem[k++]=Lb.elem[j++];
    }
    while (i < La.length) Lc.elem[k++] = La.elem[i++];
    while (j < Lb.length) Lc.elem[k++] = Lb.elem[j++];
}

// Begin define the functions of Linklist

typedef struct Lnode{
    ElemType data;
    Lnode *next;
}Lnode, *LinkList;

typedef struct Lnode_circle{
    ElemType num;
    ElemType passwd;
    Lnode_circle *next;
}Lnode_circle, *LinkList_circle;

void print_link(LinkList L, bool isCircle = 0, bool isTable = 0) {
    LinkList p = L->next;
    int i=0;
    if (! isCircle){
        while(++i && p) {
            if (! isTable){
                cout<<"Element "<<i<<"==\t"<<p->data<<endl;
                p = p->next;
            }
            else {
                cout<<"Element "<<i<<"==\t"<<char(p->data)<<endl;
                p = p->next;

            }
        }
    }
    else {
        while(++i && p != L) {
            cout<<"Element "<<i<<"==\t"<<p->data<<endl;
            p = p->next;
        }
    }
}

void CreateList_L(LinkList &L, int n, bool isCircle = 0) {
    L = (LinkList) malloc(sizeof(Lnode));
    if (!isCircle) L->next = NULL;// isCircle
    else L->next = L;
    LinkList new_one;
    for (int i = n; i > 0; --i) {
        new_one = (LinkList) malloc(sizeof(Lnode));
        cout<<"Please input the\t"<<i<<"th elemnt: "<<endl;
        ElemType e;
        cin>>e;
        new_one->data = e;
        new_one->next = L->next;
        L->next = new_one;
    }
}

Status ListInsert_L(LinkList &L, int i, ElemType e) {
    LinkList p = L;
    int j = 0;
    while (++j < i && p) p = p->next;
    if (j == i) {
        LinkList new_one;
        new_one = (LinkList) malloc(sizeof(Lnode));
        new_one->data = e;
        new_one->next = p->next;
        p->next = new_one;
        return OK;
    }
    else{
        cout<<"Waring from function ListInsert_L: illegal i\tj\t"<<i<<'\t'<<j<<endl;
        return ERROR;
    }
}

Status ListInsert_L_t(LinkList &L, int i, ElemType e) {
    LinkList p = L;
    if(i<1) return ERROR;
    for (int j=0;j<i;j++){
        if(!p){
            cout<<"ERROR"<<endl;
            return ERROR;
        }
        if(j!=i-1) p=p->next;
    }


    //for (int j=1;j<i;++j) {
        //if(!p) {
            //cout<<"Waring from function ListInsert_L: illegal i\tj\t"<<i<<'\t'<<j<<endl;
            //return ERROR;
        //}
        //p=p->next;
    //}
    LinkList new_one=(LinkList)malloc(sizeof(Lnode));
    new_one->data=e;
    new_one->next=p->next;
    cout<<"new_one inited"<<endl;
    p->next=new_one;
    return OK;
}

Status ListDelete_L(LinkList &L, int i) {
    LinkList p = L;
    int j = 0;
    while (p && j < i-1) {p = p->next;++j;}
    if (j == i-1 && p->next) {
        //cout<<"p->data\t"<<p->data<<endl;
        //cout<<"p->next->data\t"<<p->next->data<<endl;
        //cout<<"p->next->next is \t"<<p->next->next<<endl;
        LinkList q = p->next;
        p->next = p->next->next;
        free(q);
        //print_link(L);
        return OK;
    }
    else {
        cout<<"Waring from function ListDelete_L: illegal i\tj\t"<<i<<'\t'<<j<<endl;
        return ERROR;
    }
}

void ListDelete_L_t(LinkList &L,int i){
    LinkList p=L;
    for (int j=0;j<i;j++){
        if(!p) {
            cout<<"ERROR"<<endl;
            return ;
        }
        if(j!=i-1) p=p->next;
    }
    if(!p->next || i<=0){
        cout<<"ERROR"<<endl;
        return ;
    }
    else{
        p->next=p->next->next;
        free(p->next);
    }

}

int LocateElem_L(LinkList L, ElemType e, int kind) {
    int pos=0;
    if      (kind == KIND_GT) {for (LinkList p=L->next; p; p=p->next,++pos) if (p->data > e)  return pos+1;}
    else if (kind == KIND_GE) {for (LinkList p=L->next; p; p=p->next,++pos) if (p->data >= e)  return pos+1;}
    else if (kind == KIND_LT) {for (LinkList p=L->next; p; p=p->next,++pos) if (p->data < e)  return pos+1;}
    else if (kind == KIND_LE) {for (LinkList p=L->next; p; p=p->next,++pos) if (p->data <= e)  return pos+1;}
    else if (kind == KIND_EQ) {for (LinkList p=L->next; p; p=p->next,++pos) if (p->data == e)  return pos+1;}
    else if (kind == KIND_NE) {for (LinkList p=L->next; p; p=p->next,++pos) if (p->data != e)  return pos+1;}
    else {
        cout<<"Warning from function compare: illegal kind "<<kind<<endl;
        return -1;
    }
    return 0;
}

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
    LinkList a = La->next,b = Lb->next;
    Lc = La;
    LinkList c = Lc;
    while (a && b){
        if (b->data < a->data) {
            c->next = b;
            c = b;
            b = b->next;
        }
        else {
            c->next = a;
            c = a;
            a = a->next;
        }
    }
    c->next = a ? a : b;
    free(Lb);
}

void test_link(){
    LinkList L;
    CreateList_L(L,0);
    for(int i=0;i<12;i++)ListInsert_L(L, 1, (i*6+i+14)%12);
    print_link(L);
    while (1){
        ElemType input_e;
        int location,kind_op,kind_fc;
        //if (kind_op){
            //cout<<"input Please!, data "<<endl;
            //cin>>input_e;
        //}
        cout<<"input Please!, kind ,1 is insert, 2 is locate ,other is delete"<<endl;
        cin>>kind_op;
        if(kind_op!=2){
            cout<<"input Please!, location "<<endl;
            cin>>location;
        }
        if (kind_op == 1) {
            cout<<"input Please!, data "<<endl;
            cin>>input_e;
            ListInsert_L_t(L,location,input_e);
            print_link(L);
        }
        else if(kind_op==2){
            cout<<"input Please!, data "<<endl;
            cin>>input_e;
            cout<<"input Please!, kind of function \n0 is >, 1 is >=, 2 is < ,3 is <=, 4 is ==, 5 is !="<<endl;
            cin>>kind_fc;
            int pos=LocateElem_L(L, input_e, kind_fc), pos_ori=0;
            while(pos>=1){
                cout<<"location =\t"<<LocateElem_L(L,input_e,kind_fc)+pos_ori++<<'\n';
                ListDelete_L(L,pos);
                pos=LocateElem_L(L, input_e, kind_fc);
            }
            cout<<'\n';
            print_link(L);
            //print_link(L);
        }
        else {
            ListDelete_L(L,location );
            print_link(L);
        }

    }
}

// Begin define the function of SLinkList

typedef struct {
    ElemType data;
    int cur;
}component,SLinkList[MAXSIZE];

void print_sl(SLinkList space, int S) {
    int i = 0;
    while (space[S].cur) {
        S = space[S].cur;
        cout<<"Element\t"<<++ i<<"\tis\t"<<space[S].data<<endl;
    }
    cout<<endl;
    //if (i) cout<<"Element\t"<<++ i<<"\tis\t"<<space[S].data<<endl;
}

void InitSpace(SLinkList &space){
    for (int i = 0; i < MAXSIZE-1; ++i) space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0;
}

int Malloc_SL(SLinkList &space) {
    int i;
    i = space[0].cur;
    if (i) space[0].cur = space[i].cur;
    return i;
}

void Free_SL(SLinkList &space, int k) {
    space[k].cur = space[0].cur;
    space[0].cur = k;
}

void difference(SLinkList &space, int &S) {
    InitSpace(space);
    S = Malloc_SL(space);
    int r = S;
    int m, n;
    cout<<"Please input two numbers  you want to deal!  ";
    cin>>m>>n;
    for(int i = 0; i < m; ++i){
        ElemType e;
        cout<<"Input the number for \t"<<i+1<<endl;
        cin>>e;
        int j = Malloc_SL(space);
        space[j].data = e;
        space[r].cur = j;
        r = j;
    }
    space[r].cur = 0;
    cout<<"After Inserted!"<<endl;
    print_sl(space, S);

    for (int i = 0; i < n; ++i) {
        ElemType e;
        cout<<"Input the number for \t"<<i+1<<endl;
        cin>>e;
        int k = S;
        int k_before = 0;
        int counter = 0;
        bool isExisted = 0;
        while (space[k].cur) {
            k_before = k;
            k = space[k].cur;
            if (space[k].data == e) {isExisted = 1;break;};
        }
        if (!isExisted ) {
            cout<<"will add"<<endl;
            int j = Malloc_SL(space);
            space[j].data = e;
            space[j].cur = 0;
            space[k].cur = j;
        }
        else{
            cout<<"will delete"<<endl;
            space[k_before].cur = space[k].cur;
        }
        print_sl(space, S);
    }
}

// Begin define the function of stack

typedef struct {
    ElemType *base;
    ElemType *top;
    int stacksize;
}SqStack;

Status InitSqStack(SqStack &S, int size_init=100){
    ElemType *new_base=(ElemType *)malloc(size_init*sizeof(ElemType));
    if (!new_base) return ERROR;
    S.base=new_base;
    S.top=new_base;
    S.stacksize=size_init;
    return OK;
}

void print_sq_stack(SqStack S){
    ElemType *p=S.top;
    int i=0;
    while (p!=S.base){
        cout<<++i<<"\tis\t"<<*p--<<'\n';
    }
}

Status Push_sq(SqStack &S, ElemType data, int size_increment=10){
    if (!S.stacksize) {
        int size_now=S.top-S.base;
        S.base=(ElemType *)realloc(S.base, (size_now+size_increment)*sizeof(ElemType));
        S.top=S.base+size_now;
        S.stacksize=size_increment;
    }
    *++S.top=data;
    S.stacksize--;
    return OK;
}

Status Pop_sq(SqStack &S, ElemType &e){
    if (S.top!=S.base) {
        e=*S.top--;
        S.stacksize++;
        return OK;
    }
    cout<<"Warning From function Pop_sq\n";
    return ERROR;
}

void test_the_stack() {
    SqStack S;
    InitSqStack (S, 2);
    while (1){
        ElemType input_e;
        int kind_op;
        cout<<"input option kind.Please! 0 is delete , 1 is insert, others break!"<<endl;
        cin>>kind_op;
        if (kind_op>1) break;
        if (kind_op == 1) {
            cout<<"input data Please! "<<endl;
            cin>>input_e;
            Push_sq(S, input_e);
        }
        else if (kind_op==0){
            if (Pop_sq(S, input_e)==OK) cout<<"The result of Pop is\t"<<input_e<<'\n';
        }
        else break;
        print_sq_stack(S);
    }
    //print_link(L, 0, 1);
    //table_insert(L, 'e');
    //cout<<endl;
    //table_delete(L, 'a');

}

void binary_conversion(int data, int bin_con){
    SqStack S;
    InitSqStack(S);
    cout<<"After Conversion ,"<<data<<" = ";
    while(data){
        Push_sq(S, data%bin_con);
        data/=bin_con;
    }
    while(S.top!=S.base){
        ElemType e;
        Pop_sq(S,e);
        cout<<e;
    }
    cout<<'\n';
}

void bracket_matching(){
    SqStack S;
    InitSqStack(S);
    int index=0;
    while (1){
        bool t=1;
        //cout<<"Begin "<<++index<<endl;
        if (S.base!=S.top) {
            cout<<"False! \n";
            //break;
        }
        char string[100];
        cout<<"Please input brackets !\n";
        cin>>string;
        if (string[0]=='b') break;
        int j=0;
        ElemType data_pop,data_unuseful;
        int f_n=0;
        while(string[j]!='\0') {
            if (string[j]=='(' || string[j]=='[') Push_sq(S,string[j]);
            else if(string[j]==')') {
                int b=Pop_sq(S,data_pop);
                if (b==ERROR) data_pop='b';
                if (data_pop!='(') {
                    cout<<"False";
                    f_n=1;
                    Push_sq(S, 'a');
                    break;
                }
                cout<<"()\t";
            }
            else if(string[j]==']') {
                int b=Pop_sq(S,data_pop);

                if (b==ERROR) data_pop='b';
                if (data_pop!='[') {
                    cout<<"False!\n";
                    f_n=1;
                    Push_sq(S, 'a');
                    break;
                }
                cout<<"[]\t";
            }
            else{
                cout<<"Metting Illegal char --- "<<string[j]<<endl;
                break;
            }
            j++;

        }
        cout<<endl;
    }
}

int weight(char op){
    if (op=='+' || op=='-') return 0;
    if (op=='*' || op=='/') return 1;
    if (op=='(' || op==')') return 2;
    cout<<"bad op "<<op<<endl;
    return -1;
}

/*void count_expression(){*/
    //char [100];
    //cout<<" !\n";
    //cin>>;
    //int i=0,num_op=0;
    //SqStack Option,Data,data_poped,option_poped;
    //InitSqStack(Option);
    //InitSqStack(Data);
    //InitSqStack(data_poped);
    ////Push_sq(Option, '#');
    ////Push_sq(Data, '#');
    //while ([i]!='\0'){
        //char d=[i++];
        //if (d=='+' || d=='-' || d =='*' || d =='/' || d=='(' || d==')') {
            //if (d==')') {
                //int num_poped_op=0;
                //while (1){
                    //char o;
                    //Pop_sq(Option, o);
                    //if (o=='(') break;
                    //num_poped_op++;
                //}
                //for(int i=0;i<num_poped_op+1;i++) {
                    //char d;
                    //Pop_sq(Data, d);
                    //Push_sq(data_poped, d);
                //}
                ////Pop_sq(Data, d1);
                ////Pop_sq(Data, d0);
                //char kind_op;

            //}
            //else {
                //Push_sq(Option, d);
                //num_op++;
            //}
        //}
        //else {
            //if (Option.top-Option.base<2) Push_sq(Data, d);
            //else {

            //}
        //}
    //}
/*}*/

 //Begin define the function of table

Status table_insert (LinkList &L,  char e){
    int int_e = int(e);
    LinkList p = L;
    LinkList p_before;
    int j = 0;
    //while (p) {
        //p_before = p;
        //p = p->next;
        //if (p->data >= int_e) {
        //}
    //}
    bool finded = 0;
    while ( p  && ++j && p->next) {
        if (p->next->data >= int_e){
            finded = 1;
            ListInsert_L(L, j, int_e);
            print_link(L, 0, 1);
            return OK;
        }
        p = p->next;
    }
    ListInsert_L(L, j, int_e);
    return OK;
}

Status table_delete (LinkList &L,  char e){
    int int_e = int(e);
    LinkList p = L;
    LinkList p_before;
    int j = 0;
    //while (p) {
        //p_before = p;
        //p = p->next;
        //if (p->data >= int_e) {
        //}
    //}
    bool finded = 0;
    while ( p  && ++j) {
        if(!p->next)break;
        if (p->next->data == int_e){
            finded = 1;
            ListDelete_L(L, j);
            print_link(L, 0, 1);
            return OK;
        }
        p = p->next;
    }
    //if (j == i) {
        //LinkList new_one;
        //new_one = (LinkList) malloc(sizeof(Lnode));
        //new_one->data = e;
        //new_one->next = p->next;
        //p->next = new_one;
        //return OK;
    //}
    {
        cout<<"Waring from function table_delete "<<endl;
        return ERROR;
    }
}

void test_the_table() {
    LinkList L;
    CreateList_L (L, 0);
    for (int i = 97+25; i > 96 ; --i){
        ListInsert_L(L, 1, i);
    }
    print_link(L, 0, 1);
    while (1){
        char input_e;
        int kind_op;
        cout<<"input option kind.Please! 0 is delete , 1 is insert, others break!"<<endl;
        cin>>kind_op;
        if (kind_op>1) break;
        cout<<"input data Please! "<<endl;
        cin>>input_e;
        if (kind_op == 1) {
            table_insert(L, input_e);
        }
        else if (kind_op==0){
            table_delete(L, input_e);
        }
        else break;
    }
    //print_link(L, 0, 1);
    //table_insert(L, 'e');
    //cout<<endl;
    //table_delete(L, 'a');

}

// Begin define the function of circle

void CreateList_L_circle(LinkList_circle &L, int n) {
    L = (LinkList_circle) malloc(sizeof(Lnode_circle));
    L->next = L;
    LinkList_circle new_one;
    int list_pd[7]={3,1,7,2,4,8,4};
    for (int i = 6; i >= 0; --i) {
        new_one = (LinkList_circle) malloc(sizeof(Lnode));
        //cout<<"Please input two\t"<<i<<"th elemnt num ,passwd: "<<endl;
        //ElemType e,f;
        //cin>>e>>f;
        new_one->num = i+1;
        new_one->passwd = list_pd[i];
        new_one->next = L->next;
        L->next = new_one;
    }
}

void print_link_circle(LinkList_circle L) {
    LinkList_circle p = L->next;
    int i=0;
    while(++i && p!=L) {
         cout<<"Element "<<i<<"==\t"<<p->num<<"\tpasswd is\t"<<p->passwd<<endl;
         p = p->next;
    }
}

void test_the_circle(int num_people=7) {
    LinkList_circle L;
    CreateList_L_circle(L, num_people);
    print_link_circle(L);
    //return ;
    int m=20;
    LinkList_circle p =L;
    int j=0,people_deaded=0;
    while(people_deaded <7){
        j++;
        if (m==j){
            m=p->next->passwd;
            //cout<<"A People Dead! and the people_deaded is \t"<<people_deaded;
            cout<<p->next->num<<'\n';
            j=0;
            people_deaded++;
            p->next=p->next->next;
            if (p->next==L) p=L;
            continue;
        }
        p=p->next;
        if (p->next==L) p=L;
    }
    //cout<<L->next->num;
}


int main(){
    //cout<<"Start demo job 1...\n";
    //test_the_table();

    //cout<<"Start demo job 2 ...\n";
    //test_the_circle(0);

    //test_the_stack();
    binary_conversion(1348,8);
    //char a[10];
    //cin>>a;
    //for (int i=0;i<5;++i) {
        //if (a[i]=='\0') {
            //cout<<"OKKKKKKK....";
            //break;
        //}
        //cout<<a[i];
    //}
    bracket_matching();
    //test_the_circle();
    return 0;

}


